package cn.bellychang.leetcode.question253;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei),
 * determine if a person could attend all meetings.
 * <p>
 * Example 1:
 * Input: [[0,30],[5,10],[15,20]]
 * Output: 2
 * <p>
 * Example 2:
 * Input: [[7,10],[2,4]]
 * Output: 1
 *
 * @author ChangLiang
 * @date 2021/3/22
 */
public class Solution {

    public int minMeetingRooms(int[][] intervals) {

        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        // 将输入的一系列会议按照会议的起始时间排序
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] - o2[0] > 0) {
                return 1;
            } else if (o1[0] == o2[0]) {
                return 0;
            } else {
                return -1;
            }
        });

        // 用一个最小堆来维护目前开辟的所有会议室
        // 最小堆里的会议室按照会议的结束时间排序 结束时间越早 最放在最小堆
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(intervals.length,
                (o1, o2) -> {
                    if (o1[1] - o2[1] > 0) {
                        return 1;
                    } else if (o1[1] == o2[1]) {
                        return 0;
                    } else {
                        return -1;
                    }
                });

        // 让第一个会议在第一个会议室中进行
        priorityQueue.offer(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            // 从第二个会议开始， 每个会议都从最小堆中取出一个会议室
            int[] interval = priorityQueue.poll();
            // 若当前要开的会议可以等会议室被腾出来才开始 那么就可以重复利用这个会议室
            if (intervals[i][0] >= interval[1]) {
                interval[1] = intervals[i][1];
            } else {
                // 否则 开辟一个新的会议室
                priorityQueue.offer(intervals[i]);
            }
            priorityQueue.offer(interval);
        }
        return priorityQueue.size();
    }
}
